package demo;

/**
 * @Author liangzai
 * @Description:
 */
import java.util.Arrays;
import java.util.Scanner;

public class Training {
    public static void main1(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int V = scanner.nextInt();
        int[] wight = new int[n+1];
        int[] val = new int[n+1];
        for (int i = 1; i <= n; i++) {
            wight[i] = scanner.nextInt();
            val[i] = scanner.nextInt();
        }
        int[][] dp = new int[n+1][V+1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= V; j++) {
                dp[i][j] = dp[i-1][j];
                if(j>=wight[i]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i][j-wight[i]]+val[i]);
                }
            }
        }
        System.out.println(dp[n][V]);
        for (int i = 0; i <= n; i++) {
            Arrays.fill(dp[i], 0);
        }
        for (int i = 1; i <= V; i++) {
            dp[0][i] = -1;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= V; j++) {
                dp[i][j] = dp[i-1][j];
                if(j>=wight[i] && dp[i][j-wight[i]]!=-1) {
                    dp[i][j] = Math.max(dp[i][j], dp[i][j-wight[i]]+val[i]);
                }
            }
        }
        System.out.println(dp[n][V]==-1?0:dp[n][V]);
    }

    //零钱兑换 2
    //(错误)
    public int change1(int amount, int[] coins) {
        int n = coins.length;
        int[][] dp = new int[n+1][amount+1];
        for (int i = 1; i <= amount; i++) {
            dp[0][i] = -1;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= amount; j++) {
                dp[i][j] = dp[i-1][j];
                if(j>=coins[i-1] && dp[i][j-coins[i-1]]!=-1) {
                    dp[i][j] += dp[i][j-coins[i-1]];
                }
            }
        }
        return dp[n][amount];
    }

    public int change(int amount, int[] coins) {
        int n = coins.length;
        int[][] dp = new int[n+1][amount+1];
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= amount; j++) {
                dp[i][j] += dp[i-1][j];
                if(j>=coins[i-1]){
                    dp[i][j] += dp[i][j-coins[i-1]];
                }
            }
        }
        return dp[n][amount];
    }


    public static void main2(String[] args) {
        String[] strs = {"10", "0001", "111001", "1", "0"};
        int ret = findMaxForm(strs, 5, 3);
        System.out.println(ret);
    }

    //一和零
    public static int findMaxForm(String[] strs, int m, int n) {
        int len = strs.length;
        int[][] nums = new int[len+1][2];
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < strs[i].length(); j++) {
                if(strs[i].charAt(j)=='0') {
                    nums[i+1][0]++;
                }else {
                    nums[i+1][1]++;
                }
            }
        }
        int[][][] dp = new int[len+1][m+1][n+1];
        for (int i = 1; i <= len; i++) {
            for (int j = 1; j <= m; j++) {
                for (int k = 1; k <= n; k++) {
                    dp[i][j][k] = dp[i-1][j][k];
                    if(j>=nums[i][0] && k>=nums[i][1]) {
                        dp[i][j][k] = Math.max(dp[i][j][k], dp[i-1][j-nums[i][0]][k-nums[i][1]]+1);
                    }
                }
            }
        }
        return dp[len][m][n];
    }

    public static void main(String[] args) {
        int ret = numSquares(12);
        System.out.println(ret);
    }

    //完全平方数
    public static int numSquares(int n) {
        int[] nums = new int[1000];
        int count = 0;
        for (int i = 1; i*i<=n; i++) {
            nums[i] = i*i;
            count++;
        }
        int[][] dp = new int[count+1][n+1];
//        for (int i = 1; i <= n; i++) {
//			dp[0][i] = 0x3f3f3f3f;
//		}
        for (int i = 1; i <= count; i++) {
            for (int j = 0; j <= n; j++) {
                dp[i][j] = dp[i-1][j];
                if(j>=nums[i]) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][j-nums[i]]+1);
                }
            }
        }
        return dp[count][n];
    }
}

